class Solution {
public:
    // 方案二：原地更新
    // 时间复杂度：O(mn)
    // 空间复杂度：O(1)
    void gameOfLife(vector<vector<int>>& board) {
            vector<vector<int>> directions = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1},
            {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

            int m = board.size();
            int n = board[0].size();

            // 遍历每个细胞，并确定它最终的状态
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                    int liveNeighbors = 0;
                    for (auto& dir : directions) {
                        int nextRow = i + dir[0];
                        int nextCol = j + dir[1];
                        if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n) {
                            if(abs(board[nextRow][nextCol]) == 1) liveNeighbors++;
                        }
                    }
                    // 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
                    if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                        board[i][j] = -1;
                    }
                    // 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

                    // 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

                    // 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
                    if (board[i][j] == 0 && liveNeighbors == 3) {
                        board[i][j] = 2;
                    }
                }
            }
            // 遍历 board 得到一次更新后的状态
            for (int row = 0; row < m; row++) {
                for (int col = 0; col < n; col++) {
                    if (board[row][col] > 0) {
                        board[row][col] = 1;
                    } else {
                        board[row][col] = 0;
                    }
                }
            }
        }

    // 方案一：使用辅助数组
    // 时间复杂度：O(mn)
    // 空间复杂度：O(mn)
    void gameOfLife1(vector<vector<int>>& board) {
        vector<vector<int>> directions = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},
        {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

        int m = board.size();
        int n = board[0].size();
        // 创建复制数组 copyBoard
        vector<vector<int>> copyBoard(m, vector<int>(n));

        // 从原数组复制一份到 copyBoard 中
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                copyBoard[i][j] = board[i][j];
            }
        }

        // 遍历每个细胞，并确定它最终的状态
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;
                for (auto& dir : directions) {
                    int nextRow = i + dir[0];
                    int nextCol = j + dir[1];
                    if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && copyBoard[nextRow][nextCol] == 1) {
                        liveNeighbors++;
                    }
                }
                // 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
                if (copyBoard[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[i][j] = 0;
                } 
                // 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

                // 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

                // 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
                if (copyBoard[i][j] == 0 && liveNeighbors == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }
};